﻿// 602 合并数列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
/*
http://oj.daimayuan.top/course/7/problem/493

有 n个线性序列，第 i个序列可以表示成 ki×x+bi的形式 (x=0,1,2,...)。

请问将这些序列中的数按从小到大的顺序合并起来，前 m
 个数分别是多少（重复出现的数合并后也会出现多次）？

输入格式
第一行一个整数 n。

接下来 n行每行两个整数 ki，bi。

最后一行一个整数 m。

输出格式
输出一行 m个整数，表示答案。

样例输入
2
1 2
5 2
8
样例输出
2 2 3 4 5 6 7 7
样例解释
两个数列分别为 2,3,4,5,6,7,8,...
 和 2,7,12,...
。

数据规模
对于 100%
 的数据，保证 1≤n≤20000,1≤m≤100000,1≤ki,bi≤1000。
*/
const int N = 20010;
int n, m;
int k[N]; int b[N];

struct RESULT {
	int res,input,id;
	bool operator < (const struct RESULT& b) const { // 这里后面的const必须加
		return res > b.res;
	}
};


priority_queue<struct RESULT> q;

 

int main()
{
	//cin >> n;
	scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d",&k[i],&b[i]);
	}
	scanf("%d",&m);

	for (int i = 0; i < n; i++) {
		int x = 0;
		int y = k[i] * x + b[i];
		q.push({ y,x,i });
	}
	int cnt = 0;
	while (cnt < m) {
		auto t = q.top(); q.pop(); cnt++;
		printf("%d ",t.res);
		int id = t.id;
		int x = t.input + 1;
		int y = k[id] * x + b[id];
		q.push({ y,x,id });
	}

	return 0;
}